/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#include <ctime>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;

//标记棋盘状态
map<string, bool> vis;
ll x_y[9] = {4, 0, 1, 2, 5, 8, 7, 6, 3};
class node
{
public:
    string s;     //记录棋盘状态
    ll id;        //记录空位置所在的位置
    ll gx, hx;    //gx记录从初始状态到当前状态的代价，hx记录当前状态到目标状态的估计代价
    node *pre;    //指向前一个状态节点
    node *son[4]; //指向当前状态节点的下一个可能状态节点（孩子指针）
    node(string temp, ll g, ll i, node *p, ll hx_choice) : s(temp), gx(g), id(i)
    {
        pre = p;
        //计算估价函数
        if (hx_choice == 0)
            get_hx_1(temp);
        else if(hx_choice==1)
            get_hx_2(temp);
        else
            hx = 0;
        //初始化孩子指针
        for (ll k = 0; k < 4; k++)
            son[k] = NULL;
    }
    void get_hx_1(string temp)
    {
        string e = "123804765";
        hx = 0;
        for (int i = 0; i < 9; i++)
        {
            if (temp[i] != e[i])
                hx++;
        }
    }
    void get_hx_2(string temp)
    {
        string e = "123804765";
        hx = 0;
        for (int i = 0; i < 9; i++)
        {
            hx += (abs((i % 3) - (x_y[temp[i] - '0'] % 3)) + abs((i / 3) - (x_y[temp[i] - '0'] / 3)));
        }
    }
};
class Compare_Node_Pointer
{
public:
    //按照总代价从小到大排序
    bool operator()(node *&a, node *&b) const
    {
        return (a->gx + a->hx) > (b->gx + b->hx);
    }
};

//状态转移方向数组
ll next_s[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

//存储状态树节点指针的优先队列
priority_queue<node *, vector<node *>, Compare_Node_Pointer> p;

//输出最优方案的状态转移路径
void print(node *ptr)
{
    if (ptr == NULL)
        return;
    print(ptr->pre);
    for (int i = 0; i < 9; i++)
    {
        if (i % 3 == 0)
            cout << endl;
        cout << ptr->s[i] << " ";
    }
    cout << endl;
    return;
}

//释放状态树的内存
void free_memory(node *ptr)
{
    if (ptr == NULL)
        return;
    for (ll i = 0; i < 4; i++)
    {
        free_memory(ptr->son[i]);
    }
    delete ptr;
    return;
}
int main()
{
    ll hx_choice,node_k,node_s;
    string s0 = "012345678";
    string e0 = "123804765";
    while (true)
    {
        cout << "起始状态(输入0退出):";
        cin >> s0;
        if(s0=="0")
            break;
        cout << "选择估价函数(0:不在位；1:错位距离和；2:无估价函数):";
        cin >> hx_choice;
        node_k =0;
        node_s = 1;
        node *root = new node(s0, 0, s0.find('0'), NULL, hx_choice); //初始状态，根节点
        vis[s0] = true;
        p.push(root);
        bool success = false; //有无解
        ll end1, st1 = clock();
        //广度优先搜索
        while (!p.empty())
        {
            node *ptr = p.top();
            node_k++;
            p.pop();
            int x = ptr->id / 3;
            int y = ptr->id % 3;
            string temp_s;
            for (ll k = 0; k < 4; k++)
            {
                end1 = clock();
                int tx = x + next_s[k][0];
                int ty = y + next_s[k][1];
                if (tx < 0 || tx > 2 || ty < 0 || ty > 2) //筛除不可能的状态
                    continue;
                temp_s = ptr->s;
                swap(temp_s[tx * 3 + ty], temp_s[x * 3 + y]);
                if (vis[temp_s]) //筛除出现过的状态
                    continue;
                vis[temp_s] = true;
                node *temp_node = new node(temp_s, ptr->gx + 1, tx * 3 + ty, ptr, hx_choice);
                ptr->son[k] = temp_node;
                //找到目标状态
                if (temp_node->s == e0)
                {

                    success = true;
                    print(temp_node); //回溯打印方案路径
                    cout << "共需要" << temp_node->gx << "步" << endl;
                    cout << "扩展节点数: " << node_k << endl;
                    cout << "生成节点数: " << node_s << endl;
                    //清空队列
                    while (!p.empty())
                    {
                        p.pop();
                    }
                    break;
                }
                node_s++;
                p.push(temp_node);
            }
        }
        cout <<"耗时：" <<(end1 - st1) * 1.0 / CLOCKS_PER_SEC << " s" << endl;
        if (!success)
            cout << "无可行解" << endl;
        //最后释放内存
        free_memory(root);
        vis.clear();
    }
    return 0;
}
//130824765
//640382157
//134826075
//456012378
